{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Binary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addBinary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个二进制字符串 <code>a</code> 和 <code>b</code> ，以二进制字符串的形式返回它们的和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>a = \"11\", b = \"1\"\n",
    "<strong>输出：</strong>\"100\"</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = \"1010\", b = \"1011\"\n",
    "<strong>输出：</strong>\"10101\"</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 仅由字符 <code>'0'</code> 或 <code>'1'</code> 组成</li>\n",
    "\t<li>字符串如果不是 <code>\"0\"</code> ，就不含前导零</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-binary](https://leetcode.cn/problems/add-binary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-binary](https://leetcode.cn/problems/add-binary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"11\"\\n\"1\"', '\"1010\"\\n\"1011\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        x, y = int(a, 2), int(b, 2)\n",
    "        while y:\n",
    "            x, y = x ^ y, (x & y) << 1\n",
    "        return bin(x)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: 'str', b: 'str') -> 'str':\n",
    "        aInt=int(a,2)\n",
    "        bInt=int(b,2)\n",
    "        return bin(aInt+bInt)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: 'str', b: 'str') -> 'str':\n",
    "        na, nb = len(a), len(b)\n",
    "        ret = ''\n",
    "        i, j = na - 1, nb - 1\n",
    "        carry = 0\n",
    "        while i >= 0 or j >= 0:\n",
    "            if i >= 0:\n",
    "                va = int(a[i])\n",
    "                i -= 1\n",
    "            else:\n",
    "                va = 0\n",
    "            if j >= 0:\n",
    "                vb = int(b[j])\n",
    "                j -= 1\n",
    "            else:\n",
    "                vb = 0\n",
    "            v = (va + vb + carry) % 2\n",
    "            carry = (va + vb + carry) // 2\n",
    "            ret = str(v) + ret\n",
    "        if carry:\n",
    "            ret = '1' + ret\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: 'str', b: 'str') -> 'str':\n",
    "        a = a[::-1]\n",
    "        b = b[::-1]\n",
    "        temp = 0\n",
    "        for i in range(len(a)):\n",
    "            temp += int(a[i])*(2**i)\n",
    "        a_value = temp\n",
    "        temp = 0\n",
    "        for i in range(len(b)):\n",
    "            temp += int(b[i])*(2**i) \n",
    "        b_value = temp\n",
    "        add_value = a_value + b_value\n",
    "        print(a_value)\n",
    "        print(b_value)\n",
    "        print(add_value)\n",
    "        result = str()\n",
    "        while add_value>=2:\n",
    "            result += str(int(add_value%2))\n",
    "            add_value = add_value//2\n",
    "        result += str(int(add_value))\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        len_a = len(a)\n",
    "        len_b = len(b)\n",
    "        result = []\n",
    "        longest = {}\n",
    "        if len_a < len_b:\n",
    "            num_min = len_a\n",
    "            longest.setdefault('a', b)\n",
    "            left = len_b-len_a\n",
    "        else:\n",
    "            num_min = len_b\n",
    "            longest.setdefault('a', a)\n",
    "            left = len_a-len_b\n",
    "        temp = 0\n",
    "        for index in range(1, num_min+1):\n",
    "            temp = temp+int(a[-index])+int(b[-index])\n",
    "            if temp >= 2:\n",
    "                result.insert(0, temp-2)\n",
    "                temp = 1\n",
    "            else:\n",
    "                result.insert(0, temp)\n",
    "                temp = 0\n",
    "        for index in range(left-1, -1, -1):\n",
    "            temp = temp+int(longest.get('a')[index])\n",
    "            if temp >= 2:\n",
    "                result.insert(0, temp-2)\n",
    "                temp = 1\n",
    "            else:\n",
    "                result.insert(0, temp)\n",
    "                temp = 0\n",
    "        if temp:\n",
    "            result.insert(0,temp)\n",
    "        return ''.join(str(x) for x in result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(eval('0b' + a) + eval('0b' + b))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        flag = 0\n",
    "        if len(a)>len(b):\n",
    "            b = '0'*(len(a)-len(b))+b\n",
    "        else:\n",
    "            a = '0'*(len(b)-len(a))+a\n",
    "        le = len(a)\n",
    "        print(a,b)\n",
    "        result = ''\n",
    "        \n",
    "        for i in range(le):\n",
    "            print(i)\n",
    "            num = int(a[le-i-1])+int(b[le-i-1])+flag\n",
    "            print('num',num)\n",
    "            if num==0:\n",
    "                result = '0'+result\n",
    "                flag = 0\n",
    "            if num==1:\n",
    "                result = '1'+result\n",
    "                flag = 0\n",
    "            if num==2:\n",
    "                result = '0'+result\n",
    "                flag = 1\n",
    "            if num==3:\n",
    "                result = '1'+result\n",
    "                flag = 1\n",
    "            if i==le-1 and flag==1:\n",
    "                result = '1'+result\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        lena=len(a)\n",
    "        lenb=len(b)\n",
    "        carry=0\n",
    "        result=[]\n",
    "        num=max(lena,lenb)\n",
    "        if num==lena:\n",
    "            b=(lena-lenb)*'0'+b\n",
    "        elif num==lenb:\n",
    "            a=(lenb-lena)*'0'+a\n",
    "        a=list(map(int,list(a)))\n",
    "        b=list(map(int,list(b)))\n",
    "        for i in reversed(range(num)):\n",
    "            if a[i]+b[i]+carry>1:\n",
    "                \n",
    "                print(i,a[i],b[i],carry,(a[i]+b[i]+carry)%2)\n",
    "                result.append((a[i]+b[i]+carry)%2)\n",
    "                carry=1\n",
    "            else:\n",
    "                \n",
    "                result.append(a[i]+b[i]+carry)\n",
    "                carry=0\n",
    "        result.append(carry)\n",
    "        print(''.join(list(map(str,result[::-1]))))\n",
    "        return str(int(''.join(list(map(str,result[::-1])))))\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return str(bin(int(a,2) + int(b,2)))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        c = 0\n",
    "        a = a[::-1]\n",
    "        b = b[::-1]\n",
    "        la = len(a)\n",
    "        lb = len(b)\n",
    "        print(a, b)\n",
    "        result = []\n",
    "        i = 0\n",
    "        while i < la or i < lb:\n",
    "            if i >= la:\n",
    "                ta = 0\n",
    "            else:\n",
    "                ta = int(a[i])  \n",
    "            if i >= lb:\n",
    "                tb = 0\n",
    "            else:\n",
    "                tb = int(b[i])\n",
    "            \n",
    "            d =  ta + tb + c\n",
    "            print(ta, tb, c, d)\n",
    "            if d < 2:\n",
    "                c = 0\n",
    "            else:\n",
    "                c = 1\n",
    "            result.append(str(d%2))\n",
    "            i += 1\n",
    "            \n",
    "        if c==1:\n",
    "            result.append('1')\n",
    "            \n",
    "        return \"\".join(result[::-1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        #入参检查\n",
    "        if len(a) == 0:\n",
    "            return b\n",
    "        elif len(b) == 0:\n",
    "            return a\n",
    "\n",
    "        #补0\n",
    "        zeros = abs(len(a) - len(b))\n",
    "\n",
    "        if len(a) >= len(b):\n",
    "            b = '0' * zeros + b\n",
    "            max_len = len(a)\n",
    "        else:\n",
    "            a = '0' * zeros + a\n",
    "            max_len = len(b)\n",
    "\n",
    "        carry = 0\n",
    "        string = ''\n",
    "        for i in range(1, max_len+1):\n",
    "            print(a[-i], b[-i])\n",
    "            sum = int(a[-i]) + int(b[-i]) + carry\n",
    "            if sum == 0:\n",
    "                string = '0' + string\n",
    "                carry = 0\n",
    "            elif sum == 1:\n",
    "                string = '1' + string\n",
    "                carry = 0\n",
    "            elif sum == 2:\n",
    "                string = '0' + string\n",
    "                carry = 1\n",
    "            else:\n",
    "                string = '1' + string\n",
    "                carry = 1\n",
    "\n",
    "        if carry:\n",
    "            string = '1' + string\n",
    "\n",
    "        return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if a == \"\" and b == \"\":\n",
    "            return \"\"\n",
    "        \n",
    "        i = a[-1] if a else \"0\"\n",
    "        j = b[-1] if b else \"0\"\n",
    "\n",
    "        k = int(i) + int(j)\n",
    "        print(k)\n",
    "        if k == 0:\n",
    "            return self.addBinary(a[0:-1], b[0:-1]) + \"0\"\n",
    "        elif k == 1:\n",
    "            return self.addBinary(a[0:-1], b[0:-1]) + \"1\"\n",
    "        elif k == 2:\n",
    "            return self.addBinary(self.addBinary(a[0:-1], b[0:-1]), \"1\") + \"0\"\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        c = 0\n",
    "        a = a[::-1]\n",
    "        b = b[::-1]\n",
    "        la = len(a)\n",
    "        lb = len(b)\n",
    "        result = []\n",
    "        i = 0\n",
    "        while i < la or i < lb:\n",
    "            if i >= la:\n",
    "                ta = 0\n",
    "            else:\n",
    "                ta = int(a[i])  \n",
    "            if i >= lb:\n",
    "                tb = 0\n",
    "            else:\n",
    "                tb = int(b[i])\n",
    "            \n",
    "            d =  ta + tb + c\n",
    "            print(ta, tb, c, d)\n",
    "            if d < 2:\n",
    "                c = 0\n",
    "            else:\n",
    "                c = 1\n",
    "            result.append(str(d%2))\n",
    "            i += 1\n",
    "            \n",
    "        if c==1:\n",
    "            result.append('1')\n",
    "            \n",
    "        return \"\".join(result[::-1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: 'str', b: 'str') -> 'str':\n",
    "        return bin(int(a, 2) + int(b, 2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution1:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ans,i,j,c = \"\",len(a)-1,len(b)-1,0\n",
    "        while i >= 0 and j >= 0:\n",
    "            tmp = int (a[i]) + int (b[j]) + c \n",
    "            ans += str(tmp%2)\n",
    "            c = tmp//2\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        while i >= 0:\n",
    "            tmp = int (a[i]) + c \n",
    "            ans += str(tmp%2)\n",
    "            c = tmp//2\n",
    "            i -= 1\n",
    "        while j >= 0:\n",
    "            tmp = int (b[j]) + c \n",
    "            ans += str(tmp%2)\n",
    "            c = tmp//2\n",
    "            j -= 1\n",
    "        ans = ans if c == 0 else ans+str(c)\n",
    "        return ans[::-1]\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(Solution().addBinary(\"1101\",\"1111\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a_ten = self.binary_ten(a)\n",
    "        b_ten = self.binary_ten(b)\n",
    "        sum_ten = a_ten + b_ten\n",
    "        sum_binary = self.ten_binary(sum_ten)\n",
    "        return sum_binary\n",
    "\n",
    "    def binary_ten(self,s ):\n",
    "        length = len(s)\n",
    "        ten_number = 0\n",
    "        for _ in range(length):\n",
    "            ten_number += int(math.pow(2, length-_-1)) * int(s[_])\n",
    "        return ten_number\n",
    "    def ten_binary(self, s):\n",
    "        if s == 0:\n",
    "            return \"0\"\n",
    "        binary_number = \"\"\n",
    "        while s > 0:\n",
    "            binary_number += str(s % 2)\n",
    "            s = s // 2\n",
    "        binary_number = binary_number[::-1]\n",
    "        return binary_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        if len(a) < len(b):\n",
    "            a,b = b,a\n",
    "        n = len(a)\n",
    "        b = (n - len(b))*'0' + b\n",
    "        res = ''\n",
    "        add = 0\n",
    "        for i in range(n):\n",
    "            num_a = int(a[n-i-1])\n",
    "            num_b = int(b[n-i-1])\n",
    "            res = str(( num_a+ num_b + add) % 2) + res\n",
    "            add = (num_a+ num_b + add) // 2 \n",
    "        if add == 1:\n",
    "            res = '1' + res\n",
    "        return res\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2) + int(b,2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        # return bin(int(a,2)+int(b,2))[2:]   bin()将数字转为二进制，int(a,2)将字符串a转为二进制整型  bint()[2:0]去掉\"0b\"取后面的数\n",
    "        sum = []\n",
    "        tmp = 0\n",
    "        a = list(a)\n",
    "        b = list(b)\n",
    "        while(len(a) and len(b)):\n",
    "            pa = int(a.pop())\n",
    "            pb = int(b.pop())\n",
    "            sum1 = str((pa+pb+tmp)%2)\n",
    "            tmp = (pa+pb+tmp) //2\n",
    "            sum.insert(0,sum1)\n",
    "        if len(a):\n",
    "            if tmp == 1:\n",
    "                while(len(a)):\n",
    "                    pa = int(a.pop())\n",
    "                    sum1 = str((tmp+pa)%2)\n",
    "                    tmp = (tmp+pa) // 2\n",
    "                    sum.insert(0,sum1)\n",
    "            else:\n",
    "                a = \"\".join(a)\n",
    "                sum.insert(0,a)\n",
    "        if len(b):\n",
    "            if tmp == 1:\n",
    "                while(len(b)):\n",
    "                    pb = int(b.pop())\n",
    "                    sum1 = str((tmp+pb)%2)\n",
    "                    tmp = (tmp+pb) // 2\n",
    "                    sum.insert(0,sum1)\n",
    "            else:\n",
    "                b = \"\".join(b)\n",
    "                sum.insert(0,b)\n",
    "        if tmp == 1:\n",
    "            sum.insert(0,'1')\n",
    "        sum = \"\".join(sum) \n",
    "        return sum \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        carry=0\n",
    "        m,n=len(a),len(b)\n",
    "        if m>n:\n",
    "            b='0'*(m-n)+b \n",
    "        else:\n",
    "            a='0'*(n-m)+a \n",
    "        res=\"\"\n",
    "        for i in range(len(a)-1,-1,-1):\n",
    "            temp=int(a[i])+int(b[i])+carry\n",
    "            if temp>=2:\n",
    "                res=str(temp-2)+res\n",
    "                carry=1\n",
    "            else:\n",
    "                res=str(temp)+res\n",
    "                carry=0\n",
    "        if carry==1:\n",
    "            res='1'+res\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        c = int(a) + int(b)\n",
    "        if not c: return '0'\n",
    "        ans = ''\n",
    "        while c >= 1:\n",
    "            rest = c % 10\n",
    "            if rest > 1:\n",
    "                ans = str(rest - 2) + ans\n",
    "                c = (c // 10) + 1\n",
    "            else:\n",
    "                ans = str(rest) + ans\n",
    "                c = c // 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b) -> str:\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        int_a = int(a)\n",
    "        int_b = int(b)\n",
    "        int_re = int_a+int_b\n",
    "        list_re = [int(i) for i in list(str(int_re))]\n",
    "        for i in range(-1,-len(list_re)-1,-1):\n",
    "            print(i,list_re[i])\n",
    "            if list_re[i] >= 2 and i > -len(list_re):\n",
    "                list_re[i] = list_re[i] -2\n",
    "                list_re[i-1] += 1\n",
    "            elif list_re[i] >= 2 and i == -len(list_re):\n",
    "                list_re[i] = list_re[i] -2\n",
    "                list_re.insert(0,1)\n",
    "        return \"\".join([str(i) for i in list_re])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        m=max(len(a),len(b))\n",
    "        a=list(reversed(list(a)))\n",
    "        b=list(reversed(list(b)))\n",
    "        if len(a) ==m:\n",
    "            b.extend(['0' for i in range(0,m-len(b)+1)])\n",
    "            a.append('0')\n",
    "        else:\n",
    "            a.extend(['0' for i in range(0,m-len(a)+1)])\n",
    "            b.append('0')\n",
    "        s=[]\n",
    "        def binaryadd(a,b,n,d):\n",
    "            while n>=0:\n",
    "                c=int(a[0])+int(b[0])+d-2\n",
    "                if c>=0:\n",
    "                    d=1\n",
    "                    s.append(str(c))\n",
    "                else:\n",
    "                    d=0\n",
    "                    s.append(str(c+2))\n",
    "                return binaryadd(a[1::],b[1::],n-1,d)\n",
    "            else:\n",
    "                if d ==1:\n",
    "                    s.append('1')\n",
    "                else:\n",
    "                    s.append('0')\n",
    "        binaryadd(a,b,m,0)\n",
    "        result=''.join(list(reversed(s)))\n",
    "        if result[0]=='0':\n",
    "            if result[1]=='0':\n",
    "                result=result[2::]\n",
    "            else:\n",
    "                result=result[1::]\n",
    "        return result\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        arr_a = list(a)\n",
    "        arr_b = list(b)\n",
    "        la = len(arr_a)\n",
    "        lb = len(arr_b)\n",
    "        \n",
    "        if la > lb:\n",
    "            arr_b = ['0' for i in range(la-lb)] + arr_b\n",
    "            \n",
    "        if lb > la:\n",
    "            arr_a = ['0' for i in range(lb-la)] + arr_a\n",
    "        \n",
    "        arr_c = ['0' for i in range(len(arr_a))]\n",
    "        next_c = '0'\n",
    "        for i in range(len(arr_a)-1, -1, -1):\n",
    "            print(arr_a[i], arr_b[i])\n",
    "            if arr_a[i] == '1' and arr_b[i] == '1':\n",
    "                if next_c == '1':\n",
    "                    arr_c[i] = '1'\n",
    "                else:\n",
    "                    arr_c[i] = '0'\n",
    "                next_c = '1'\n",
    "            elif (arr_a[i] == '1' and arr_b[i] == '0') or (arr_a[i] == '0' and arr_b[i] == '1'):\n",
    "                if next_c == '1':\n",
    "                    arr_c[i] = '0'\n",
    "                    next_c = '1'  \n",
    "                else:\n",
    "                    arr_c[i] = '1'\n",
    "            elif arr_a[i] == '0' or arr_b[i] == '0':\n",
    "                if next_c == '1':\n",
    "                    arr_c[i] = '1'                    \n",
    "                else:\n",
    "                    arr_c[i] = '0' \n",
    "                next_c = '0'  \n",
    "\n",
    "        if next_c == '1':\n",
    "            arr_c = ['1'] + arr_c\n",
    "            \n",
    "        return ''.join(str(i) for i in arr_c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a = int(a,2)\n",
    "        b = int(b,2)\n",
    "\n",
    "        c = a+b\n",
    "        c = bin(c)\n",
    "        return c[2::]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res = \"\"\n",
    "        i, j, carry = len(a) - 1, len(b) - 1, 0\n",
    "        while i >= 0 or j >= 0:\n",
    "            sum = carry\n",
    "            sum += ord(a[i]) - ord(\"0\") if i >= 0 else 0\n",
    "            sum += ord(b[j]) - ord(\"0\") if j >= 0 else 0\n",
    "            res += str(sum % 2)\n",
    "            carry = sum // 2\n",
    "            i, j = i - 1, j - 1\n",
    "        if carry > 0:\n",
    "            res += str(carry)\n",
    "        return res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        flag = 0\n",
    "        c = \"\"\n",
    "        for i in range(-1, - min(len(a), len(b)) - 1, -1):\n",
    "            temp = int(a[i]) + int(b[i]) + flag\n",
    "            c += str(temp % 2)\n",
    "            flag = temp // 2\n",
    "        if len(a) > len(b):\n",
    "            for i in a[-len(b) - 1::-1]:\n",
    "                temp = int(i) + flag\n",
    "                c += str(temp % 2)\n",
    "                flag = temp // 2\n",
    "        else:\n",
    "            for i in b[-len(a) - 1::-1]:\n",
    "                temp = int(i) + flag\n",
    "                c += str(temp % 2)\n",
    "                flag = temp // 2\n",
    "        if flag == 1:\n",
    "            c += \"1\"\n",
    "        return c[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        flag = 0\n",
    "        c = \"\"\n",
    "        for i in range(-1, - min(len(a), len(b)) - 1, -1):\n",
    "            temp = int(a[i]) + int(b[i]) + flag\n",
    "            c += str(temp % 2)\n",
    "            flag = temp // 2\n",
    "        if len(a) > len(b):\n",
    "            for i in a[-len(b) - 1::-1]:\n",
    "                temp = int(i) + flag\n",
    "                c += str(temp % 2)\n",
    "                flag = temp // 2\n",
    "        else:\n",
    "            for i in b[-len(a) - 1::-1]:\n",
    "                temp = int(i) + flag\n",
    "                c += str(temp % 2)\n",
    "                flag = temp // 2\n",
    "        if flag == 1:\n",
    "            c += \"1\"\n",
    "        return c[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def addBinary(self, a: str, b: str) -> str:\r\n",
    "        s = []\r\n",
    "        c = 0\r\n",
    "        for i in range(max(len(a), len(b))):\r\n",
    "            bit_a = int(a[-i-1]) if i < len(a) else 0\r\n",
    "            bit_b = int(b[-i-1]) if i < len(b) else 0\r\n",
    "            sum = bit_a + bit_b + c\r\n",
    "            s.append(str(sum % 2))\r\n",
    "            c = 1 if sum >= 2 else 0\r\n",
    "        if c == 1:\r\n",
    "            s.append('1')\r\n",
    "        return \"\".join(s[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2) + int(b,2))[2:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2) + int(b,2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ab = int(a) + int(b)\n",
    "        dp = [0] + list(map(int,str(ab)))\n",
    "        for i in range(len(dp)-1,-1,-1):\n",
    "            if dp[i] >= 2:\n",
    "                dp[i-1] += dp[i] // 2\n",
    "                dp[i] -= 2\n",
    "        if a == '0' and b == '0':\n",
    "            return '0'\n",
    "        return(''.join(map(str, dp)).lstrip('0'))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
